package _02_并查集;
/*
    Quick Find
    ✓ 查找（Find）的时间复杂度：O(1)
    ✓ 合并（Union）的时间复杂度：O(n)
 */
public class QuickFind extends UnionFind {
    public QuickFind(int capacity) {
        super(capacity);
    }

    /**
     * 查找v所属的集合(根节点)
     * O(1)
     * @param v
     * @return 返回它所存储的元素即可，也就是根节点
     */
    @Override
    public int find(int v){
        rangeCheck(v);
        return parents[v];
    }

    /**
     * 合并v1,v2所属的集合,将v1合并到v2
     * 如果v1之前属于了一个集合，那么将整个数组都和v1属于同一个集合的元素都合并到v2
     * @param v1
     * @param v2
     */
    @Override
    public void union(int v1,int v2){
        int p1 = find(v1);
        int p2 = find(v2);
        if(p1 == p2) return; //属于同一个集合，不用合并

        for (int i = 0; i < parents.length; i++) {
            if(parents[i] == p1){
                parents[i] = p2;
            }
        }
    }
}
